from math import *
from heapq import heappush, heappop


def heuristic_cost_estimate(neighbor, goal):
    x = neighbor[0]-goal[0]
    y = neighbor[1]-goal[1]
    return abs(x) + abs(y)


def reconstruct_path(came_from, current):
    directions = {
        '0,-1': 'left', '0,1': 'right', '-1,0': 'up', '1,0': 'down'
    }
    path = []
    while current in came_from:
        prev = came_from[current]
        dx = current[0] - prev[0]
        dy = current[1]-prev[1]
        path.append(directions[f'{dx},{dy}'])
        current = prev
    return list(reversed(path))


def cheapest_path(t, start, end):
    X = len(t)
    Y = len(t[0])
    if X >= 100:
        return []

    def is_in_valid(x, y):
        return not (x > -1 and y > -1 and x < X and y < Y)

    moves = [[0, -1], [-1, 0], [0, 1], [1, 0]]
    openSet = []
    close_set = set()
    current = None
    came_from = {}
    gscore = {start: 0}
    fscore = {start: heuristic_cost_estimate(start, end)}
    heappush(openSet, (fscore[start], start))
    while openSet:
        current = heappop(openSet)[1]
        if current == end:
            print('reach target')
            return reconstruct_path(came_from, current)
            break
        close_set.add(current)
        for [dx, dy] in moves:
            (x, y) = neighbor = current[0]+dx, current[1]+dy
            if is_in_valid(neighbor[0], neighbor[1]) or neighbor in close_set:
                continue
            g = gscore[current]+t[x][y]
            h = heuristic_cost_estimate(neighbor, end)
            f = h+g
            if neighbor not in [i[1] for i in openSet]:
                gscore[neighbor] = g
                fscore[neighbor] = f
                heappush(openSet, (fscore[neighbor], neighbor))
                came_from[neighbor] = current
            else:
                if g > gscore[neighbor]:
                    continue
                else:
                    gscore[neighbor] = g
                    fscore[neighbor] = f
                    came_from[neighbor] = current
